import java.util.*;

public class Offer38 {
    String str;

    public String SetToStr(Set<Integer> tmpStr){
        StringBuilder sb=new StringBuilder();
        for (Integer num:tmpStr) {
            sb.append(str.charAt(num));
        }
        return sb.toString();
    }
    
    public void travel(Set<String> res, Set<Integer> tmpStr){
        if(tmpStr.size()==str.length()){
            res.add(SetToStr(tmpStr));
        }
        for (int i = 0; i < str.length(); i++) {
            if(!tmpStr.contains(i)) {
                tmpStr.add(i);
                travel(res, tmpStr);
                tmpStr.remove(i);
            }
        }
    }

    public String[] permutation(String s) {
        this.str=s;
        Set<String> res=new HashSet<>();
        Set<Integer> tmpStr=new LinkedHashSet<>();
        travel(res,tmpStr);
        String[] probRes=new String[res.size()];
        int ind=0;
        for (String str:res) {
            probRes[ind++]=str;
        }
        return probRes;
    }
}
